package com.dexter.year2023.charpter2_reverselinklist.level2.topic2_1指定区间反转;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 92. 反转链表 II ★
 * https://leetcode.cn/problems/reverse-linked-list-ii/
 * <p>
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表结点，返回 反转后的链表 。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * 示例 2：
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 * <p>
 * 提示：
 * 链表中结点数目为 n
 * 1 <= n <= 500
 * -500 <= Node.val <= 500
 * 1 <= left <= right <= n
 * <p>
 * 进阶： 你可以使用一趟扫描完成反转吗？
 *
 * @author Dexter
 */
public class ReverseBetween {
    public static void main(String[] args) {
        // 链表初始化
        int[] a = {1, 2, 3, 4, 5};
        Node head = initLinkedList(a);
        int left = 2, right = 4;
        // 测试方法
        int testMethod = 2;
        Node reverseHead = null;
        switch (testMethod) {
            case 1:
                reverseHead = reverseList(head);
                break;
            case 2:
                reverseHead = reverseBetween(head, left, right);
                break;
            case 3:
                reverseHead = reverseBetween2(head, left, right);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }
        printLinkedList(reverseHead);
    }

    /**
     * 反转链表基础写法，level1的法2
     *
     * @param head
     * @return
     */
    public static Node reverseList(Node head) {
        // 不涉及虚拟结点
        Node pre = null;
        Node cur = head;
        // 移动cur，反向
        while (cur != null) {
            // cur下一个要去的位置
            Node next = cur.next;
            // cur反向
            cur.next = pre;
            // pre移动
            pre = cur;
            // cur移动
            cur = next;
        }
        return pre;
    }

    // region 本节方法

    /**
     * 法1：头插法
     *
     * @param head  待反转链表头结点
     * @param left  位置left，头从1开始算
     * @param right 位置right
     * @return
     */
    public static Node reverseBetween(Node head, int left, int right) {
        // 涉及虚拟结点
        Node dummy = new Node(-1);
        dummy.next = head;
        // 从dummy开始寻找，要走到left的位置开始反转
        Node pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 到left的前一个了，cur是left
        Node cur = pre.next;
        // 定义next，暂存cur下一结点信息
        Node next;
        for (int i = 0; i < right - left; i++) {
            // cur 交出next位的信息
            next = cur.next;
            // cur 去 next的下一位
            cur.next = next.next;
            // next 接到 pre 后面
            next.next = pre.next;
            // pre 与 next 相连
            pre.next = next;
        }
        return dummy.next;
    }

    /**
     * 法2：穿针引线法
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public static Node reverseBetween2(Node head, int left, int right) {
        // 涉及虚拟结点
        Node dummy = new Node(-1);
        dummy.next = head;
        Node pre = dummy;
        // 移动pre去寻找 left - 1 位置
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 寻找 right 位置，起点是left位置
        Node rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }
        // 断开
        Node leftNode = pre.next;
        Node succ = rightNode.next;
        rightNode.next = null;
        // 交给基本反转方法
        reverseList(leftNode);
        // 拼接
        pre.next = rightNode;
        leftNode.next = succ;
        return dummy.next;
    }

    // endregion
}
